#include "PPR.h"
#include "boost\algorithm\string\predicate.hpp"

//////////////////////////////////////////////////////////////////////////
//Author	:	Ross Conroy ross.contoy@tees.ac.uk
//Date		:	07/07/2014
//
//Container for PPR representations and also performs operations on the
//PPR tree representation
//
//Update	:	24/08/2014
//Fill in missing branches using compatibility test
//////////////////////////////////////////////////////////////////////////

PPR::PPR(void)
{
	
}

PPR::PPR(ActionNode * rootActionNode)
{
	_rootNode = rootActionNode;
}

ActionNode * PPR::GetRootNode()
{
	return _rootNode;
}

//////////////////////////////////////////////////////////////////////////
//Determines if a branch can merge with the current branch using the
//following rules
//1.Must not already match/toString() function must not return same value
//2.Root node must be the same
//3.Second tree must not conflict with current tree i.e. an observation
//	must not give a differing answer
//4.Branch must fit in where there is a gap in the tree. i.e. fit in where
//	a node had no child node for a given observation
//////////////////////////////////////////////////////////////////////////
bool PPR::CanMergeWithBranch(PPR branch)
{
	bool canMerge = true;

	//Check for same root node
	if((_rootNode->GetNodeName() != branch.GetRootNode()->GetNodeName()) || (_rootNode->GetState() != branch.GetRootNode()->GetState()))
	{
		canMerge = false;
		return canMerge;
	}

	//Check not already both identical
	//if(_rootNode->ToString() == branch.GetRootNode()->ToString())
	//{
	//	canMerge = false;
	//	return canMerge;
	//}

	list<string> treeObservations = _rootNode->GetObservations();
	hash_map<string, ActionNode*> treeChildren = _rootNode->GetChildNodes();
	hash_map<string, ActionNode*> branchChildren = branch.GetRootNode()->GetChildNodes();

	bool treeEnd = true;
	for(list<string>::iterator it = treeObservations.begin(); it!= treeObservations.end(); it++)
	{
		string observation = *it;
		if((treeChildren[observation] != NULL) || (treeChildren[observation] != NULL))
		{
			treeEnd = false;
		}
	}

	while(!treeEnd)
	{
		//loops through each of the existing trees children to see if the branch can fit
		//or already matches, loops through each of the observations to compare the trees
		//child nodes with the branches child node		
		for(list<string>::iterator it = treeObservations.begin(); it!= treeObservations.end(); it++)
		{
			string observation = *it;

			//Fist check if tree has a child
			if(treeChildren[observation] != NULL)
			{
				//check if branch has a child
				if(branchChildren[observation] != NULL)
				{
					//Compare that both child nodes are the same action
					ActionNode * treeNode = treeChildren[observation];
					ActionNode * branchNode = branchChildren[observation];

					if(treeNode->GetNodeName() == branchNode->GetNodeName())
					{
						//continue searching tree, set next child
						treeChildren = treeNode->GetChildNodes();
						branchChildren = branchNode->GetChildNodes();
					}
					else
					{
						//Cant possibly match if conflicting action observation pairs
						return false;
					}
				}//else do nothing, branch may be somewhere else on tree
			}
			else
			{
				//now check if branch has a child where there is a gap
				if(branchChildren[observation] != NULL)
				{
					//Gap found
					return true;
				}
			}			
		}

		//ToDo Follow branch for next node
		treeEnd = true;
		for(list<string>::iterator it = treeObservations.begin(); it!= treeObservations.end(); it++)
		{
			string observation = *it;
			if((treeChildren[observation] != NULL) || (treeChildren[observation] != NULL))
			{
				treeEnd = false;
			}
		}
	}

	if(!canMerge)
	{
		cout << "error" << endl;
	}

	return canMerge;
}

//////////////////////////////////////////////////////////////////////////
//Merges a branch into the current tree using the following algorithm
//1.Find point where branch fills in an empty child node slot
//1.1LOOP TODO
//2.Remove parents from branch where fits with empty child node becoming
//	new root node
//3.Set new root nodes parent node to that with the empty child node
//////////////////////////////////////////////////////////////////////////
lastMerge PPR::MergeWithBranch(PPR branch)
{
	lastMerge last;

	list<string> treeObservations = _rootNode->GetObservations();
	hash_map<string, ActionNode*> treeChildren = _rootNode->GetChildNodes();
	hash_map<string, ActionNode*> branchChildren = branch.GetRootNode()->GetChildNodes();

	bool treeEnd = !((treeChildren.size() > 0) && (branchChildren.size() > 0));

	ActionNode * treeNode = _rootNode;
	ActionNode * branchNode = branch.GetRootNode();

	//_rootNode->IncrementOccurrences();

	while(!treeEnd)
	{
		//treeNode->IncrementOccurrences();
		//loops through each of the existing trees children to see if the branch can fit
		//or already matches, loops through each of the observations to compare the trees
		//child nodes with the branches child node	
		bool next = false; //indicates when to move to next level

		for(list<string>::iterator it = treeObservations.begin(); (it!= treeObservations.end())&&(!next); it++)
		{
			string observation = *it;

			//Fist check if tree has a child
			if(treeChildren[observation] != NULL)
			{
				//check if branch has a child
				if(branchChildren[observation] != NULL)
				{
					//Compare that both child nodes are the same action
					treeNode = treeChildren[observation];
					//treeNode->IncrementOccurrences();
					branchNode = branchChildren[observation];

					if(treeNode->GetNodeName() == branchNode->GetNodeName())
					{
						//continue searching tree
						treeChildren = treeNode->GetChildNodes();
						branchChildren = branchNode->GetChildNodes();
						next = true;
					}
					//else Cant possibly match if conflicting action observation pairs
				}//else do nothing, branch may be somewhere else on tree
			}
			else
			{
				//now check if branch has a child where there is a gap
				if(branchChildren[observation] != NULL)
				{
					//_branchLastParent = branchChildren[observation]->GetParent();
					//
					//_lastMergedChildNode = branchChildren[observation];
					//_lastMergedChildPreviousParent = _lastMergedChildNode->GetParent();

					last.lastMergedChildNode = branchChildren[observation];
					last.lastMergedChildPreviousParent = branchChildren[observation]->GetParent();
					last.lastMergedObservation = observation;

					branchChildren[observation]->SetParent(treeNode);
					treeChildren = treeNode->GetChildNodes();
					treeChildren[observation] = branchChildren[observation];
					treeNode->SetChildNodes(treeChildren);
					//treeNode->IncrementOccurrences();
					//_lastMergedNode = treeNode;
					//_lastMergedObservation = observation;
					//Gap found
					treeEnd = true;
					treeNode->CalculateOcurances();
				}
			}			
		}

		if(!treeEnd)
		{
			treeEnd = !((treeChildren.size() > 0) && (branchChildren.size() > 0));
			if(treeEnd)
			{
				treeNode->IncrementOccurrences();
				treeNode->GetParent()->CalculateOcurances();
			}
		}		
	}

	//treeNode->IncrementOccurrences();
	//treeNode->GetParent()->CalculateOcurances();

	return last;
}

//////////////////////////////////////////////////////////////////////////
//Reverts the last merge by setting the child nodes of the where the 
//merge occurred with an observation to NULL to indicate where no link
//Also puts branch back together that was broken for merge
//////////////////////////////////////////////////////////////////////////
void PPR::RevertLastMerge(lastMerge last)
{
	if((last.lastMergedChildNode != NULL) && (last.lastMergedChildPreviousParent != NULL))
	{
		ActionNode *pt = last.lastMergedChildNode->GetParent();

		last.lastMergedChildNode->SetParent(last.lastMergedChildPreviousParent);

		hash_map<string, ActionNode*> ptChildren = pt->GetChildNodes();
		ptChildren[last.lastMergedObservation] = NULL;
		pt->SetChildNodes(ptChildren);
	}


	/*if(_lastMergedChildNode != NULL)
	{
		_lastMergedChildNode = _rootNode;
		_lastMergedChildNode->SetParent(_lastMergedChildPreviousParent);
	}*/
	//if(_lastMergedNode != NULL)
	//{
		//if(_lastMergedChildNode != NULL)
		//{
		//	_lastMergedNode = _lastMergedChildNode->GetParent();
		//	_lastMergedChildNode->SetParent(_branchLastParent);
		//}
		///*ActionNode * child = _lastMergedNode->GetChildNodes()[_lastMergedObservation];
		//if(child != NULL)
		//{
		//	child->SetParent(_branchLastParent);
		//}*/		
		//hash_map<string, ActionNode*> treeChildren = _lastMergedNode->GetChildNodes();
		//treeChildren[_lastMergedObservation] = NULL;
		//_lastMergedNode->SetChildNodes(treeChildren);
	//}	
}

OcurancesOfAction PPR::GetOcurancesOfActionFromSearchString(string searchString)
{
	OcurancesOfAction oca;

	oca.ocurances = 0;
	oca.action = "NOT FOUND";

	stringstream ss;
	ss << searchString << ",";
	searchString = ss.str();

	vector<string> elements;
	while (searchString.find(",", 0) != string::npos)
	{
		size_t  pos = searchString.find(",", 0);
		string temp = searchString.substr(0, pos);
		searchString.erase(0, pos + 1);
		elements.push_back(temp);
	}

	string modelStr = elements[0];

	if(boost::starts_with(_rootNode->GetState(),modelStr))
	{
		//Follow tree for action and ocurances
		if(elements.size() > 1)
		{
			ActionNode * currentNode = _rootNode;

			for(int i = 1; i < elements.size(); i++)
			{
				if(((i%2) != 0) && (currentNode != NULL))
				{
					if(currentNode->GetNodeName() != elements[i])
					{
						//doesn't fit branch so return empty
						oca.ocurances = 0;
						oca.action = "NOT FOUND";
						return oca;
					}
				}
				else
				{
					//move onto next action
					currentNode = currentNode->GetChildNodes()[elements[i]];
					if(currentNode == NULL)
					{
						oca.ocurances = -1;
						oca.action = "NO CHILD";
						return oca;
					}
				}
				oca.action = currentNode->GetNodeName();
				oca.ocurances = currentNode->GetOcurances();
			}
		}
		//if only has model information then must be first node so only report action of root
		else
		{
			oca.action = _rootNode->GetNodeName();
			oca.ocurances = _rootNode->GetOcurances();
		}
	}	

	return oca;
}

//////////////////////////////////////////////////////////////////////////
//Looks to find nodes that are compatible with nodes that have branches 
//with empty nodes from them this is achieved by linking at the parent
//of a node with an empty branch. Then the parent of this branch is
//compared with other nodes of the same level to determine if any of them
//are compatible with the current branch with missing nodes
//
//Update 28/08/2014
//Fix to compatibility checks to match compatibility test in paper
//////////////////////////////////////////////////////////////////////////
int PPR::FillInMissingBranches(double epsilon)
{
	//loop through all nodes in tree checking isComplete() on each to build a list of incomplete nodes
	list<ActionNode*> nodes = _rootNode->ToListOfNodes();
	int merges = 0;

	for(list<ActionNode*>::iterator it = nodes.begin(); it != nodes.end(); it++)
	{
		ActionNode * nodeA = *it;
		
		for(list<ActionNode*>::iterator itn = nodes.begin(); itn != nodes.end(); itn++)
		{
			ActionNode * nodeB = *itn;
			if (nodeA->IsCompatible(nodeB, epsilon))
			{				
				//cout << "Compatible Node Found" << endl;
				if(nodeB->CloneMerge(nodeA))
				{
					//cout << "Merged With Compatible Node" << endl;
					merges++;
				}
			}
		}
	}

	return merges;
}